package xyf.p08.backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * ClassName: P0017_LetterCombinations
 * Description:
 * Author: xyf
 * Date: 9/8/22 9:37 AM
 * Version: 1.0
 **/
public class P0017_LetterCombinations
{
    public List<String> letterCombinations(String digits)
    {
        Map<Character, String> helpMap = new HashMap<>();
        helpMap.put('2', "abc");
        helpMap.put('3', "def");
        helpMap.put('4', "ghi");
        helpMap.put('5', "jki");
        helpMap.put('6', "mno");
        helpMap.put('7', "pqrs");
        helpMap.put('8', "tuv");
        helpMap.put('9', "wxyz");

        List<String> res = new ArrayList<>();
        backtrack(helpMap, res, digits, 0, new StringBuilder());
        return res;
    }

    public void backtrack(Map<Character, String> helpMap, List<String> res, String digits, int index, StringBuilder sb)
    {
        if (index == digits.length())
        {
            res.add(sb.toString());
            return;
        }

        String s = helpMap.get(digits.charAt(index));
        for (int j = 0; j < s.length(); j++)
        {
            sb.append(s.charAt(j));
            backtrack(helpMap, res, digits, index + 1, sb);
            sb.deleteCharAt(index);
        }
    }
}
